/*
题目：二叉树的前序遍历
 */
class PreOrderTraversalA {
    public List<Integer> preorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<> ();
        List<Integer> ans = new ArrayList<> ();

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                ans.add(root.val);
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            root = root.right;
        }

        return ans;
    }
}
/*
题目：二叉树的中序遍历
 */
public class InorderTraversalA {
    public List<Integer> inorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> ans = new ArrayList<>();

        while (root != null || !stack.isEmpty()) { //根节点不为空，并且栈不为空
            while (root != null) { //直接走到底
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            ans.add(root.val);
            root = root.right;
        }

        return ans;
    }
}
/*
题目：二叉树的后序遍历
 */
class PostorderTraversalA {
    public List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<> ();
        List<Integer> ans = new ArrayList<> ();
        TreeNode prev = null;//记录上一次经过的叶子节点

        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            //如果没有右节点或者已经经过了右节点
            if (root.right == null || root.right == prev) {
                ans.add(root.val);
                prev = root;
                root = null;//没有右子树了，置空保证当前根节点是下一个弹出
            } else { //如果有右节点，那么这个节点就不着急访问，需要再压入栈
                stack.add(root);
                root = root.right;//进入右子树
            }
        }

        return ans;
    }
}